import java.util.LinkedList;

public class Maze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    private static int enterX = 1;
    private static int enterY = 0;
    private static int exitX = 7;
    private static int exitY = 8;
    private static int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static LinkedList<String> stack = new LinkedList<>();
    private static boolean[][] visited = new boolean[9][9];

    public static void main(String[] args) {
        if(go(enterX, enterY)) {
            System.out.println("找到出口！");
            System.out.println(stack);
        } else {
            System.out.println("找不到出口");
        }
    }

    private static boolean go(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        visited[x][y] = true;
        if (x == exitX && y == exitY) {
            return true;
        }
        for (int i = 0; i < direction.length; i++) {
            int nx = x + direction[i][0];
            int ny = y + direction[i][1];
            if (isInArea(nx, ny) && isRoad(nx,ny) && !visited[nx][ny]) {
                if(go(nx,ny)) {
                    return true;
                }
            }
        }
        stack.pop();
        return false;
    }

    private static boolean isRoad(int x, int y) {
        return maze[x][y] == 0;
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < 9 && y >= 0 && y < 9;
    }
}